The present invention relates to circuits for sorting data according to a predetermined criterion and particularly to a circuit enabling to sort the k greatest data among sequentially incoming data.
Such sorting circuits are for example useful in the field of image compression systems. Indeed, in this field, it is desired to transmit as few data as possible representing an image in the best possible way. In particular, data are cancelled according to a predetermined criterion in order to increase the compression efficiency while decreasing the complexity and processing time which increase along with the number of non-null data.
In image compression systems, images are divided into blocks, for example 8.times.8 pixels, associated with matrices, each coefficient of which represents the luminance and chrominance information of a pixel. These matrices are subject, for example, to a discrete cosine transform (DCT); then, one obtains transformed matrices of equal size, the advantage of which is to have many practically null coefficients.
It has been noticed that by cancelling a certain number of small coefficients of the transformed matrix, then by submitting this matrix to a reverse cosine transform, it was possible to restore an image without significant degradation.
A first technique of the prior art for providing the greatest coefficients of the transformed matrix consists of sequentially reading the coefficients and comparing them with a threshold value in order to cancel the coefficients that are smaller than the threshold. The drawback of this technique is that all the coefficients of a matrix are cancelled if they are too small; this causes significant degradation of the restored image because the largest of such small coefficients carry a significant information. Another drawback is that none of the coefficients are cancelled if they all are larger than the threshold; in this case the desired compression is not achieved.
Another approach consists of keeping only a predetermined number k of the largest data values. This prevents cancellation of small values, that are nevertheless representative of the image, and also ensures that no more than k data values will have to be processed during subsequent steps. The known circuits for implementing this technique have had the drawback of being complex and relatively slow.
The disclosed inventions provides a simple method for implementing this other technique.